<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>最短路径</title>
    <style>
        table{
            margin: 0 auto;
        }
        .center{
            text-align: center;
        }
        td{
            width: 100px;
            height: 100px;
        }
    </style>
</head>
<body>
    <div id="app">
        <h2 class="center">Matrix</h2>
        <table border="1">
            <tr v-for="row in matrix">
                <td v-for="item in row">
                    {{ item }}
                </td>
            </tr>
        </table>
        <h2 class="center">dis and adj</h2>
        <table border="1">
            <tr>
                <td>vertex</td>
                <td v-for="(item, index) in dis">{{ index }}</td>
            </tr>
            <tr>
                <td>dis</td>
                <td v-for="item in dis">{{ item }}</td>
            </tr>
            <tr>
                <td>adj</td>
                <td v-for="it in adj">{{ it }}</td>
            </tr>
        </table>
    </div>
    <script src="https://cdn.jsdelivr.net/npm/vue/dist/vue.js"></script>
    <script>
        var dis = [];
        var adj = [];
        var visit = [];
        function printPath(adj, index){
            var stack = [];
            var printString = "";
            for(let i = index; i != -1; i = adj[i]){
                stack.push(i);
            }
            for(let i = stack.length-1; i >= 0; i--){
                if(i == 0)
                    printString += stack[i];
                else
                    printString += (stack[i]+"==>");
            }
            console.log(printString);
        }

        function Dijkstra(matrix, start){
            var n = matrix.length;
            //init dis, adj, visit
            for(let i = 0; i < n; i++){
                dis[i] = 0x3f3f3f3f;
                adj[i] = -1;
                visit[i] = 0;
            }
            var nextStart = -1;
            visit[start] = 1;
            dis[start] = 0;
            for(let i = 0; i < n; i++){
                var min = 0x3f3f3f3f;
                for(let j = 0; j < n; j++){
                    if(visit[j] != 1 && dis[start] + matrix[start][j] < dis[j]){
                        dis[j] = dis[start] + matrix[start][j];
                        adj[j] = start;
                        if(dis[j] < min){
                            min = dis[j];
                            nextStart = j;
                        }
                    }
                }
                start = nextStart;
                visit[start] = 1;
            }
            console.log(dis);
            console.log(adj);
            for(let i = 0; i < n; i++)
                printPath(adj, i);
        }

        var matrix = [
            [0, 9, 2, 0x3f3f3f3f, 6],
            [9, 0, 3, 0x3f3f3f3f, 0x3f3f3f3f],
            [2, 3, 0, 5, 0x3f3f3f3f],
            [0x3f3f3f3f, 0x3f3f3f3f, 5, 0, 1],
            [6, 0x3f3f3f3f, 0x3f3f3f3f, 1, 0]
        ];

        Dijkstra(matrix, 0);
    </script>
    <script>
        var app = new Vue({
            el: "#app",

            data:{
                matrix: matrix,
                dis: dis,
                adj: adj,
            }
        })
    </script>
</body>
</html>